import time


def show(r):
    li = sorted(r.items(), key=lambda x: (x[1]), reverse=True)
    for ele in li:
        print("%s:%.3f,\t" % (ele[0], ele[1]), end='')
    print()


def personalRank(G, a, root, max_step):
    rank = {x: 0 for x in G.keys()}
    rank[root] = 1
    # 开始迭代
    begin = time.time()
    # 最多 max_step次迭代
    for k in range(max_step):
        tmp = {x: 0 for x in G.keys()}
        # 取节点i和它的出边尾节点集合ri
        for i, ri in G.items():
            # 取节点i的出边的尾节点j以及边E(i,j)的权重wij
            s = 0
            for w in ri.values():
                s += w
            for j, wij in ri.items():
                # i是j的其中一条入边的首节点，因此需要遍历图找到j的入边的首节点，
                # 这个遍历过程就是此处的2层for循环，一次遍历就是一次游走
                tmp[j] += a * rank[i] * (wij / s)  # 考虑边的权重
        # 我们每次游走都是从root节点出发，因此root节点的权重需要加上(1 - alpha)
        tmp[root] += (1 - a)
        rank = tmp  # 一轮性的整体替换
        show(rank)
    end = time.time()
    print('use time', end - begin)
    return rank


if __name__ == '__main__':
    alpha = 0.8
    G = {'A': {'a': 1, 'c': 1},
         'B': {'a': 1, 'b': 3, 'c': 3, 'd': 4},
         'C': {'c': 1, 'd': 1},
         'a': {'A': 1, 'B': 1},
         'b': {'B': 1},
         'c': {'A': 1, 'B': 1, 'C': 1},
         'd': {'B': 1, 'C': 1}}

    personalRank(G, alpha, 'B', 50)  # 从'b'节点开始游走

# https://www.cnblogs.com/zhangchaoyang/articles/5470763.html
